#include <iostream>
using namespace std;

template<typename T>
void shell_sort(T array[], int length)
{
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                cout << "i: " << i << ", j: " << j << ", h: " << h << endl;
                std::swap(array[j], array[j - h]);
            }
            for(int i = 0; i < length; i++) {
                cout << array[i] << ' ';
            }
            cout << endl << endl;
        }
        h = h / 3;
    }
}


int main()
{
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    shell_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl << endl;
    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (float) sizeof(arrf) / sizeof(*arrf);
    shell_sort(arrf, len);
    for (int i = 0; i < len; i++)
        cout << arrf[i] << ' ';
    cout << endl;
    return 0;
}